5880. МEX

Знаешь, как это сложно — нажать на курок?

Знаменитый диктатор Ли Сий Сын имеет в своём распоряжении армию из 10⁵ человек. Он пронумеровал их от 0 до 10⁵ – 1. Чем меньший номер имеет человек, тем выше его командирские способности. Затем он репрессировал n из них. Теперь диктатор собирается провести маленькую победоносную войну с соседним государством. Поэтому ему нужно срочно выбрать самого талантливого военного из оставшихся в живых.

Вход. В первой строке находится количество репрессированных n (1 ≤ n < 10⁵). Вторая строка содержит их номера в списке Ли Сий Сына — все числа меньше 10⁵.

Выход. Выведите одно число – номер самого талантливого из живых военных.

Пример входа	Пример выхода
8 3 0 1 7 2 4 6 17	5

РЕШЕНИЕ

сортировка подсчетом

Анализ алгоритма

Пусть cnt – целочисленный массив длины 10⁵. Для каждого значения x из входного списка репрессированных установим cnt[x] = 1.

Далее следует найти наименьший индекс i, для которого cnt[i] = 0. Число i – наименьшее, которое отсутствует во входном наборе данных. Число i и будет номером самого талантливого из живых военных.

Пример

Рассмотрим состояние массива cnt после обработки всех данных входного теста.

Наименьшим числом, которое отсутствует во входном массиве, будет 5, так как cnt[5] = 0. При этом 5 – наименьший индекс, для которого соответствующая ячейка массива равна 0.

Реализация алгоритма

Объявим массив для подсчета.

#define MAX 100001

int cnt[MAX];

Читаем входные данные. Для каждого значения x из входных номеров репрессированных установим cnt[x] = 1.

scanf("%d", &n);

for (i = 0; i < n; i++)

{

scanf("%d", &x);

cnt[x] = 1;

}

Ищем наименьшее неотрицательное целое число, которого нет во входном списке. Для этого следует найти наименьшее i (i ≥ 0), для которого cnt[i] = 0.

for (i = 0; i < MAX; i++)

if (cnt[i] == 0)

{

printf("%d\n", i);

break;

}